package top100.twopointer;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/26 9:54
 * @description:
 */
public class Solution287 {
    //二分法的实现方式
    public int findDuplicate(int[] nums) {
        int min = 1;
        int max = nums.length;
        while (min < max) {
            int mid = (min + max) / 2;
            //计数
            int cnt = 0;
            for (int v : nums) {
                if (v >= min && v <= mid) {
                    cnt++;
                }
            }
            if (cnt > mid - min + 1) {//个数超过范围长度，即存在重复的数
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }

    //快慢指针的解法
    //将 i 和 nums[i] 视为链表中的父子节点，一直传递下去，nums[i]相当于next指针，因为nums[0]不等于0 所有可以将初始指针在nums[0]
    public int findDuplicate2(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (true) {
            //fast 前进两次,slow前进一次
            fast = nums[fast];
            fast = nums[fast];
            slow = nums[slow];
            if (fast == slow) break;

        }
        //ptr == slow 时候说明检测到重复元素，两个重复元素同时指向环的入口
        int ptr = 0;
        while (ptr != slow) {
            ptr = nums[ptr];
            slow = nums[slow];
        }
        return ptr;
    }

    public static void main(String[] args) {
        Solution287 solution = new Solution287();
        int[] nums = new int[]{1, 3, 4, 2, 2};
        System.out.println(solution.findDuplicate(nums));
    }
}
